대규모 서비스를 지탱하는 기술 (5 ~ 6)

ordilov / 2022. 3. 16

데이터가 대량으로 있더라도 국소성을 발견하고 그에 맞게 구성을 변경해서 속도를 높여왔습니다. 하지만 전문 검색이나, 유사문서, 데이터마이닝의 경우 광범위한 데이터에 액세스해야 합니다. 데이터의 어느 부분만 절단할 수 없을 때 어떻게 해야 할까요?

이런 경우 대부분 RDBMS로는 한계가 있기에 배치처리로 RDBMS에서 별도로 인덱스 서버를 만듭니다. 웹 어플리케이션 서버에서 인덱스 서버에 RPC등으로 접근하는 방법을 사용합니다. RPC(Remote Procedure Call)는 웹 API와 비슷하게 네트워크로 함수를 호출해 값을 받습니다.

RDBMS를 사용하면 데이터를 정렬하거나, 통계처리, JOIN등을 범용적으로 만들 수 있습니다. 하지만 뭔가 특정한 목적으로 사용하는 경우 특정 목적 튜닝 데이터 구조를 사용하면 압도적으로 빠릅니다. 이럴 때 용도 특화형 인덱스를 사요하면 자연어 처리나 검색등을 더 빠르게 처리할 수 있습니다.

문자열 키워드를 처리하기 위해선 Trie 기받느이 정규표현등을 이용해서 다양한 알고리즘과 데이터 구조로 사전에 만들어둡니다. 카테고리 자동 분류의 경우에도 기계학습이나 알고리즘이 추가로 필요합니다. 전문 검색엔징의 경우 어떤 문서를 상위로 가져올지 스코어링 처리가 필요합니다. 이 같은 기능은 특정 칼럼으로만 정렬되는 RDBMS에서는 무리로 다른 검색 인덱스가 필요합니다.

많은 것들이 고전적인 이론으로 해결할 수 있는 반면에 실전적인 노하우로 해결하는 경우도 있습니다. RDBMS의 JOIN을 사용하지 않는 것은 RDB를 본질적인 개념을 부정하는 것 아닌가 할 수 있습니다. 하지만 분할을 위해서 실전적인 방법으로 처리할 수 있기에 균형을 맞추는 것이 필요합니다. 이론을 너무 추구하다면 구현할 때 여러 단점들이 나오게 되고, 실전만 추구하면 어려운 문제를 마주쳤을 때 해결법을 모릅니다. 즉 잔재주로 작은 문제는 해결할 수 있지만 큰 문제가 되갈수록 고전적인 이론이 더 필요해집니다. 예를 들어 키워드 링크의 경우 Trie로 Common Prefix Search 알고리즘을 적용시켜야할 때 알고리즘을 모르면 해결하기 힘듭니다. 이럴 때 알고리즘과 데이터 구조를 알고 있고, 이런 구조로 해결가능한지 알아야 문제를 마주쳤을 때 해결가능한지 파악할 수 있습니다.

단순히 바이너리로 변환하는 게 아니라 부호화를 연구해서 크기를 절반 이하로 하는 것이 과제입니다. 큰 데이터를 압축해서 컴팩트하게 만들면 디스크 I/O를 줄일 수 있습니다. RDBMS에서도 정수를 적당히 작은 크기로 줄이듯이 말이죠. 여기서 신경써야 할 부분은 데이터형의 크기, 바이너리의 크기, 스크립트 언어가 갖는 데이터 크기의 오버헤드입니다.

VB Code(Variable Byte Code, 가변길이 바이트 부호)는 정수열을 압축하는 알고리즘입니다. VB Code는 구현에서 간단하고 속도가 빨라 손쉽게 사용할 수 있습니다. 컴퓨터에서 바이너리 부호는 5를 0...0101로 표현하듯이 고정길이의 비트로 부호화합니다. VB Code도 이처럼 정수를 부호화하는데 앞부분의 안쓰이는 바이트를 제외하고 최소한의 바이트로 표현합니다. 첫 1비트는 플래그로 남은 7비트로 바이너리 부호를 표현합니다. 5라면 10000101이 되고 130이라면 00000001 10000010이 됩니다. 첫 비트가 1이 아니라면 다음 바이트가 있다는 것으로 해석하면 됩니다. 이렇게 압축하면 고정 4바이트로 표현하던 바이트가 각각 1바이트, 2바이트로 표현할 수 있습니다. 값이 적으면 적을 수록 적은 바이트로 정수를 표현할 수 있는 것이 VB Code입니다.

이런 값들을 정렬된 상태에서 더 압축할 수 있습니다. [3, 5, 20] 이런 식이라면 그 사이의 차이를 이용해 [3, 2, 15]로 차로 값을 표현할 수 있습니다. 복원할 때는 처음부터 값을 생성해서 더해가면 원래 값으로 복원이 가능합니다. 값의 차이를 이용하면 원래 크기보다 더 작은 값들이 만들어져 압축률이 더 높아집니다.

압축의 기초는 출현빈도를 보고 빈번하게 출현하는 기호에 더 짧은 기호를, 그렇지 않은 기호에 긴 부호를 부여합니다. 모스 신호도 영어에서 자주 사용하는 기호는 짧고, 자주 사용하지 않는 문자는 긴 부호가 할당되어 있습니다. 모든 기호에 같은 길이의 부호를 부여하는 게 아니라 출현빈도에 따라 부여할 때 압축효과가 올라갑니다.

문자 기호인 경우 허프만 부호등을 이용해 확률 분포에 최적인 부호를 생성합니다. 하지만 이번 과제처럼 정수인 경우 문자 자체에 의미가 없기 때문에 차이를 이용하는 등 값을 변형해서 압축이 가능합니다.